A
弱智题,枚举即可。
Code
#include <cstdio>
const int N = 105;
int a[N], n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
if (a[i] == a[j] + a[k] && j != k) {
printf("%d %d %d\n", i, j, k);
return 0;
}
}
puts("-1");
}
B
字符串模拟题,讨论判断一下即可。
Code
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool check(string s) {
if (s[0] == '@' || s[s.size() - 1] == '@') return false;
int cnt = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '@') cnt++;
}
if (cnt == 0) return false;
for (int i = 1; i < s.size() - 1; i++) {
if (s[i - 1] == '@' && s[i + 1] == '@' || s[i] == '@' && s[i + 1] == '@')
return false;
}
return true;
}
int main() {
string s;
cin >> s;
if (!check(s)) {
puts("No solution");
return 0;
}
while (s.size()) {
int pos = s.find('@');
cout << s.substr(0, pos + 2);
s = s.substr(pos + 2);
if (s.find('@') != -1) cout << ",";
}
}
C
先按照左端点排序,枚举被删掉的课程,剩下的扫一遍判断是否有重叠即可。
时间复杂度 。
Code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 5005;
struct Node {
int l, r, id;
} p[N];
bool operator <(Node a, Node b) {
return a.l < b.l || a.l == b.l && a.r < b.r;
}
int n, cnt, ans[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i;
}
sort(p + 1, p + n + 1);
p[0] = {0, 0};
for (int i = 1; i <= n; i++) {
int ok = 1;
for (int j = 1; j <= n; j++) {
if (j == i) continue;
if (p[j].l < p[j - 1 - (j == i + 1)].r) ok = 0;
}
if (ok) cnt++, ans[cnt] = p[i].id;
}
sort(ans + 1, ans + cnt + 1);
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++) printf("%d%c", ans[i], " \n"[i == cnt]);
}
D
注意到切割出来每一块一定都是矩形,于是把每一条切割线转化为在被切开的方格之间按方向打上标记,爆搜记录连通块大小即可。
时间复杂度 。
Code
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 105;
const int d[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int vis[N][N], f[N][N][4], ans[N * N], n, m, w, h, cnt;
void cut(int x1, int y1, int x2, int y2) {
if (y1 == y2) {
if (x1 > x2) swap(x1, x2);
int j = y1;
for (int i = x1; i < x2; i++) {
f[i + 1][j][0] = 1;
f[i + 1][j + 1][1] = 1;
}
}
if (x1 == x2) {
if (y1 > y2) swap(y1, y2);
int i = x1;
for (int j = y1; j < y2; j++) {
f[i][j + 1][2] = 1;
f[i + 1][j + 1][3] = 1;
}
}
}
bool in(int x, int y) {
return 1 <= x && x <= w && 1 <= y && y <= h;
}
void dfs(int x, int y) {
vis[x][y] = 1;
cnt++;
for (int dir = 0; dir < 4; dir++) {
if (f[x][y][dir]) continue;
int tx = x + d[dir][0];
int ty = y + d[dir][1];
if (!vis[tx][ty] && in(tx, ty)) dfs(tx, ty);
}
}
int main() {
scanf("%d%d%d", &w, &h, &n);
for (int i = 1, x1, x2, y1, y2; i <= n; i++) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
cut(x1, y1, x2, y2);
}
for (int i = 1; i <= w; i++)
for (int j = 1; j <= h; j++)
if (!vis[i][j]) {
cnt = 0;
dfs(i, j);
ans[++m] = cnt;
}
sort(ans + 1, ans + m + 1);
for (int i = 1; i <= m; i++) printf("%d%c", ans[i], " \n"[i == m]);
}
E
以下内容为照搬题解
直接暴力 肯定过不了,考虑dp 。
令 为选择 的前 位,其中有 位接到 后面,其余接到 后面的 最大值。
但是这个东西需要考虑 和 分别为多少,没有办法转移,我们考虑从后往前推。
令 为从第 到 位中选择 位接到 后面,其余接到 后面的 最大值.
易知接到 后面的数共 位,从而有
最后搜索判断决策点并输出方案,时间复杂度 。
注意需要开 unsigned long long 。
Code
#include <algorithm>
#include <cstdio>
using namespace std;
typedef unsigned long long uint64;
const int N = 50;
uint64 f[N][N], p[N], n;
char s[N];
void dfs(int i, int j) {
if (i == 2 * n + 1) return;
if (j && f[i][j] == f[i + 1][j - 1] + p[j] * (s[i] - '0'))
putchar('H'), dfs(i + 1, j - 1);
else
putchar('M'), dfs(i + 1, j);
}
int main() {
scanf("%d%s", &n, s + 1);
p[0] = 1;
for (int i = 1; i <= n * 2; i++) p[i] = p[i - 1] * 10;
for (int i = n * 2; i >= 1; i--) {
for (int j = 0; j + i - 1 <= n * 2; j++) {
int k = n * 2 - (j + i - 1);
if (j) f[i][j] = max(f[i][j], f[i + 1][j - 1] + p[j] * (s[i] - '0'));
if (k) f[i][j] = max(f[i][j], f[i + 1][j] + p[k] * (s[i] - '0'));
}
}
dfs(1, n);
}